package shuxue;

import java.util.Arrays;

/**
 * 统计范围n内的素数个数
 * @author Administrator
 *
 */
public class CountPrime {

	public static void main(String[] args) {
		int n =88;
		System.out.println(countPrime2(n));
	}
	
	
	/**
	 * 埃氏筛法	
	 * @param n
	 * @return
	 */
	public static int countPrime2(int n) {
		if(n<=1) return 0;//特例处理
		//创建一个标志位数组，表明n范围内每个数是否是素数,True为素数，false为合数
		boolean[] isPrime = new boolean[n+1];
		//假定所有的数都是素数
		Arrays.fill(isPrime, true);
		//将isPrime[0]和isPrime[1] 置为false
		isPrime[0] = false;
		isPrime[1] = false;
		
		//根据埃氏筛法，将已知素数的K倍代表的数字置为false O(nlogn)
		for(int i=2;i<=n;i++) {//从2到100，遍历每一个数字
			if(isPrime[i]==true) {//当前的数字i是素数
				//将i的倍数置为false
				for(int j=2;j*i<=n;j++) {//j代表i的倍数 2,4,6,8， 3,5,7，
					isPrime[i*j] = false;
				}
			}
		}
		//统计isPrime中true的数量，就是素数的数量
		int count = 0;
		for(int i=0;i<=n;i++) {
			if(isPrime[i] == true){
				count++;
			}
		}
		return count;
	}
	
	
	/**
	 * 朴素算法：判断0到n之间存在多少个素数，时间复杂度O(n^2)
	 * @param n
	 * @return
	 */
	public static int countPrime1(int n) {
		int count = 0;
		for(int i=0;i<=n;i++) {
			if(isPrime(i)) {
				//System.out.println(i);
				count++;
			}
		}
		return count;
	}
	
	/**
	 * 判断n是否为素数
	 * @param n
	 * @return
	 */
	public static boolean isPrime(int n) {
		if(n<=1) return false;//特例处理
		for(int i=2;i*i<=n;i++) if(n%i==0) return false;
		return true;		
	}

}
